package leetcodev1.数组;

public class LeetCode33 {

    //半有序的数组 改进版的二分查找
    //思路1：将这个数组直接改造成全有序的
    //基于[0,x]有序 [x+1,n]有序的特点改造二分查找
    //且nums[n]<nums[0]

    //情况分析
    //mid=中间数 x=分界线
    //1.nums[mid]==target return
    //2.nums[mid]<target 在[0,mid]或者[x,n]上找
    //3.nums[mid]>target 在[mid,x]上找

    //最关键的是无论从那个位置切分，至少保证了一个区间的有序
    //这里最关键的就是nums[0]nums[length-1] 通过这个游标进行判断
    //最关键的是参照物
    public int search(int[] nums, int target) {
        int n = nums.length;

        if (n == 0) {
            return -1;
        }

        if (n == 1) {
            return nums[0] == target ? 0 : -1;
        }

        if (nums[0] == target) {
            return 0;
        }

        if (nums[n - 1] == target) {
            return n - 1;
        }

        int left = 0, right = n - 1, mid;
        while (left <= right) {
            mid = left + (right - left) / 2;
            //结束条件1
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[0] <= nums[mid]) {
                //mid<x

                if (nums[0] < target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                //mid>=x

                if (target < nums[n - 1] && nums[mid] < target) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
}
